{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Grumpy Bookstore Owner"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSatisfied"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #爱生气的书店老板"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个书店老板，他的书店开了&nbsp;<code>n</code>&nbsp;分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 <code>n</code> 的整数数组 <code>customers</code> ，其中 <code>customers[i]</code> 是在第 <code>i</code> 分钟开始时进入商店的顾客数量，所有这些顾客在第 <code>i</code> 分钟结束后离开。</p>\n",
    "\n",
    "<p>在某些时候，书店老板会生气。 如果书店老板在第 <code>i</code> 分钟生气，那么 <code>grumpy[i] = 1</code>，否则 <code>grumpy[i] = 0</code>。</p>\n",
    "\n",
    "<p>当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。</p>\n",
    "\n",
    "<p>书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续&nbsp;<code>minutes</code>&nbsp;分钟不生气，但却只能使用一次。</p>\n",
    "\n",
    "<p>请你返回 <em>这一天营业下来，最多有多少客户能够感到满意</em> 。<br />\n",
    "&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>书店老板在最后 3 分钟保持冷静。\n",
    "感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>customers = [1], grumpy = [0], minutes = 1\n",
    "<strong>输出：</strong>1</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == customers.length == grumpy.length</code></li>\n",
    "\t<li><code>1 &lt;= minutes &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= customers[i] &lt;= 1000</code></li>\n",
    "\t<li><code>grumpy[i] == 0 or 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [grumpy-bookstore-owner](https://leetcode.cn/problems/grumpy-bookstore-owner/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [grumpy-bookstore-owner](https://leetcode.cn/problems/grumpy-bookstore-owner/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,1,2,1,1,7,5]\\n[0,1,0,1,0,1,0,1]\\n3', '[1]\\n[0]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        ans = sum(customers)\n",
    "        if len(customers) < 4:\n",
    "            return ans\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i] == 0:\n",
    "                customers[i] = 0\n",
    "        mx = sum(customers[:minutes])\n",
    "        x = mx\n",
    "        for j in range(minutes,len(customers)):\n",
    "            x += -customers[j-minutes] + customers[j]\n",
    "            mx = max(x,mx)\n",
    "        return ans - sum(customers) + mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:\n",
    "        rewards = [customers[i]*grumpy[i] for i in range(len(grumpy))]\n",
    "        left_sum_list = [0,]\n",
    "        s = 0\n",
    "        for v in rewards:\n",
    "            s += v\n",
    "            left_sum_list.append(s)\n",
    "\n",
    "\n",
    "        max_reward = 0\n",
    "        max_start_pos = 0\n",
    "        for i in range(1, len(left_sum_list)):\n",
    "            start_pos = i - 1\n",
    "            right = min(len(left_sum_list)-1, i + X - 1)\n",
    "            r = left_sum_list[right] - left_sum_list[start_pos]\n",
    "            if r > max_reward:\n",
    "                max_reward = r\n",
    "                max_start_pos = start_pos\n",
    "\n",
    "        for i in range(max_start_pos, min(len(grumpy), max_start_pos + X)):\n",
    "            grumpy[i] = 0\n",
    "        res = sum([customers[i]*(1-grumpy[i]) for i in range(len(grumpy))])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:\n",
    "        origin = []\n",
    "        ori = 0\n",
    "        for i in range(X):\n",
    "            ori += (1-grumpy[i])*customers[i]\n",
    "        origin.append(ori)\n",
    "        for i in range(X,len(customers)):\n",
    "            if grumpy[i-X]==0:\n",
    "                ori -= customers[i-X]\n",
    "            if grumpy[i] == 0:\n",
    "                ori += customers[i]\n",
    "            origin.append(ori)\n",
    "        current = [sum(customers[:X])]\n",
    "        cur = current[0]\n",
    "        for i in range(X,len(customers)):\n",
    "            cur = cur - customers[i-X]+customers[i]\n",
    "            current.append(cur)\n",
    "        compare = [current[i]-origin[i] for i in range(len(current))]\n",
    "        res = 0\n",
    "        for i in range(len(customers)):\n",
    "            res += (1-grumpy[i])*customers[i]\n",
    "        return max(compare)+res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:\n",
    "        stat = [0] * len(customers)\n",
    "        stat[0] = (1-grumpy[0]) * customers[0]\n",
    "        for i in range(1, len(customers)):\n",
    "            stat[i] = stat[i-1] + (1-grumpy[i]) * customers[i]\n",
    "        sums = [0] * len(customers)\n",
    "        sums[0] = customers[0]\n",
    "        for i in range(1, len(customers)):\n",
    "            sums[i] = sums[i-1] + customers[i]\n",
    "        # print(stat)\n",
    "        ans = -1e7\n",
    "        for i in range(0, len(customers) - X + 1):\n",
    "            left = right = 0 \n",
    "            anger = 0\n",
    "            if i > 0:\n",
    "                left = stat[i-1]\n",
    "            if i + X < len(customers) :\n",
    "                right = stat[-1] - stat[i + X - 1]\n",
    "            if i > 0:\n",
    "                anger = sums[i+X-1] - sums[i-1] + left + right\n",
    "            else:\n",
    "                anger = sums[i+X-1] + left + right\n",
    "            # print(right, left, anger)\n",
    "            ans = max(anger, ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        pre = [0]\n",
    "        n = len(customers)\n",
    "        for i in range(n):\n",
    "            pre.append(pre[-1] + customers[i])\n",
    "        ha = [0]\n",
    "        for i in range(n):\n",
    "            ha.append(ha[-1] + (1 - grumpy[i]) * customers[i])\n",
    "        ans = 0\n",
    "        for r in range(minutes - 1,n):\n",
    "            z = pre[r + 1] - pre[r - minutes + 1]\n",
    "            left = ha[r - minutes + 1] + ha[-1] - ha[r + 1]\n",
    "            ans = max(ans,z + left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 滑动窗口\n",
    "# 先把能选的都选上，然后维护一个区间记录当前区间非法的最大和\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not grumpy[i]:\n",
    "                ans += customers[i]\n",
    "                customers[i] = 0\n",
    "                \n",
    "        i, j, t, mt = 0, 0, 0, 0\n",
    "        while j < n:\n",
    "            t += customers[j]\n",
    "            if j - i + 1 > minutes:\n",
    "                t -= customers[i]\n",
    "                i += 1\n",
    "            j += 1\n",
    "            mt = max(mt, t)\n",
    "\n",
    "        return ans + mt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        ans = sum(customers)\n",
    "        if len(customers) < 4:\n",
    "            return ans\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i] == 0:\n",
    "                customers[i] = 0\n",
    "        mx = sum(customers[:minutes])\n",
    "        x = mx\n",
    "        for j in range(minutes,len(customers)):\n",
    "            x += -customers[j-minutes] + customers[j]\n",
    "            mx = max(x,mx)\n",
    "        return ans - sum(customers) + mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n=len(customers)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if grumpy[i]==0:\n",
    "                res+=customers[i]\n",
    "                customers[i]=0\n",
    "        am=0\n",
    "        mm=0\n",
    "        for i in range(n):\n",
    "            mm+=customers[i]\n",
    "            if i>=minutes:\n",
    "                mm-=customers[i-minutes]\n",
    "            am=max(mm,am)\n",
    "        return am+res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        max_list = []\n",
    "        count = 0\n",
    "        max_count = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        num = 0\n",
    "        while right < len(customers):\n",
    "            if right - left < minutes:\n",
    "                if grumpy[right] == 1:\n",
    "                    count += customers[right]\n",
    "                right += 1\n",
    "            else:\n",
    "                if count > max_count:\n",
    "                    max_list = [i for i in range(left, right)]\n",
    "                    max_count = count\n",
    "                if grumpy[left] == 1:\n",
    "                    count -= customers[left]\n",
    "                left += 1\n",
    "        if count > max_count:\n",
    "            max_list = [i for i in range(left, right)]\n",
    "        for j in max_list:\n",
    "            grumpy[j] = 0\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i] == 0:\n",
    "                num += customers[i]\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:\n",
    "        t=0\n",
    "        for i in range(len(grumpy)):#记录下一定满意的顾客数，并把不影响的地方去掉\n",
    "            if grumpy[i]==0:\n",
    "                t+=customers[i]\n",
    "                customers[i]=0\n",
    "\n",
    "        n=sum(customers[:X])#滑动窗口找连续X个的最大值\n",
    "        m=n\n",
    "        for i in range(1,len(customers)-X+1):\n",
    "            m=m+customers[i+X-1]-customers[i-1]\n",
    "            n=max(m,n)\n",
    "            #print(n)\n",
    "        return n+t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        ans, n = 0, len(grumpy)\n",
    "        for i in range(n):\n",
    "            if grumpy[i] == 0:\n",
    "                ans += customers[i]\n",
    "                customers[i] = 0\n",
    "        mx, cur = 0, 0\n",
    "        for i in range(n):\n",
    "            cur += customers[i]\n",
    "            if (i >= minutes):\n",
    "                cur -= customers[i - minutes]\n",
    "            mx = max(mx, cur)\n",
    "        return mx + ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        slen = len(customers)\n",
    "        customers = [0] + customers\n",
    "        grumpy = [0] + grumpy\n",
    "        if slen <= minutes:\n",
    "            return sum(customers)\n",
    "        max_count_per_minutes, counter = 0, 0\n",
    "        pre_sum, pre_sum_gru = [0] * (1 + slen), [0] * (1 + slen)\n",
    "        for i in range(1, slen + 1):  # forwarding counting\n",
    "            counter += 1\n",
    "            pre_sum[i] = pre_sum[i - 1] + customers[i]\n",
    "            pre_sum_gru[i] = pre_sum_gru[i - 1] if grumpy[i] else\\\n",
    "                pre_sum_gru[i - 1] + customers[i]\n",
    "            if counter >= minutes:\n",
    "                max_count_per_minutes = max(max_count_per_minutes,\n",
    "                                            (pre_sum[i] - pre_sum[i - minutes])\n",
    "                                            - (pre_sum_gru[i] -\n",
    "                                               pre_sum_gru[i - minutes]))\n",
    "        return pre_sum_gru[-1] + max_count_per_minutes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        mymax = tmp = pre = 0\n",
    "        for i in range(0, len(customers)):\n",
    "            if grumpy[i] == 0:\n",
    "                pre += customers[i]\n",
    "                customers[i] = 0\n",
    "            else:\n",
    "                tmp += customers[i]\n",
    "            if i >= minutes:\n",
    "                tmp -= customers[i-minutes]\n",
    "            mymax = max(mymax, tmp)\n",
    "        return pre + mymax\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        count=0\n",
    "        dq=deque()\n",
    "        max_count=0\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i]==0:\n",
    "                count+=customers[i]\n",
    "            else:\n",
    "                dq.append([i,customers[i]])\n",
    "            \n",
    "            if dq:\n",
    "                while dq[-1][0]-dq[0][0]+1>minutes:\n",
    "                    dq.popleft()\n",
    "                max_count=max(max_count,sum([i[1] for i in dq]))\n",
    "                # print(max_count,dq)\n",
    "\n",
    "        return count+max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        angry=[]\n",
    "        time=[]\n",
    "        for i in range(len(grumpy)):\n",
    "            if grumpy[i]==1:\n",
    "                time.append(i)\n",
    "                angry.append(customers[i])\n",
    "        ans=[]\n",
    "        for start in range(len(grumpy)-minutes+1):   #冷静时间【start,start+minutes-1]\n",
    "            left=bisect_left(time,start)\n",
    "            right=bisect_right(time,start+minutes-1)\n",
    "            cur=sum(angry[left:right])\n",
    "            ans.append(cur)\n",
    "        An=max(ans)\n",
    "        stillangry=sum(angry)-An\n",
    "        return sum(customers)-stillangry\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        ans = [customers[0]]\n",
    "        raw_acc = [customers[0] * (1 - grumpy[0])]\n",
    "        for i in range(1, minutes):\n",
    "            ans.append(ans[-1] + customers[i])\n",
    "            raw_acc.append(raw_acc[-1] + customers[i] * (1 - grumpy[i]))\n",
    "        for i in range(minutes, len(customers)):\n",
    "            raw_acc.append(raw_acc[-1] + customers[i] * (1 - grumpy[i]))\n",
    "            if grumpy[i] == 0:\n",
    "                ans.append(ans[-1] + customers[i])\n",
    "            else:\n",
    "                ans.append(max(raw_acc[i-minutes]+sum(customers[i-minutes+1:i+1]), ans[-1]))\n",
    "\n",
    "        return ans[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n=len(customers)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if grumpy[i]==0:\n",
    "                res+=customers[i]\n",
    "                customers[i]=0\n",
    "        am=0\n",
    "        mm=0\n",
    "        for i in range(n):\n",
    "            mm+=customers[i]\n",
    "            if i>=minutes:\n",
    "                mm-=customers[i-minutes]\n",
    "            am=max(mm,am)\n",
    "        return am+res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(grumpy)):\n",
    "            res += customers[i]*(1-grumpy[i])\n",
    "            customers[i] *= grumpy[i]\n",
    "        temp = mx = 0\n",
    "        for i in range(minutes):\n",
    "            temp += customers[i]\n",
    "        mx = temp\n",
    "        for i in range(minutes, len(grumpy)):\n",
    "            temp += (customers[i]-customers[i-minutes])\n",
    "            mx = max(mx, temp)\n",
    "        return res+mx\n",
    "\n",
    "        \n",
    "        res = sum(customers)\n",
    "        customers = [customers[i]*grumpy[i] for i in range(len(grumpy))]\n",
    "        res -= sum(customers)\n",
    "        temp = mx = sum(customers[:minutes])\n",
    "        for i in range(minutes, len(grumpy)):\n",
    "            temp += (customers[i]-customers[i-minutes])\n",
    "            mx = max(mx, temp)\n",
    "        return res+mx\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        #res1\n",
    "        res = 0\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i]==0:\n",
    "                res += customers[i]\n",
    "                customers[i] = 0\n",
    "        res1 = float('-inf')\n",
    "        l,r,cur = 0,0,0\n",
    "        while r<len(customers):\n",
    "            cur += customers[r]\n",
    "            if r-l+1>=minutes:\n",
    "                res1 = max(res1,cur)\n",
    "                cur-=customers[l]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return res+res1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if grumpy[i] == 0:\n",
    "                total += customers[i]\n",
    "                customers[i] = 0\n",
    "        left = 0\n",
    "        right = minutes\n",
    "        increase = 0\n",
    "        while left < right <= n:\n",
    "            temp = sum(customers[left:right])\n",
    "            increase = max(increase, temp)\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return total + increase"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        #res1\n",
    "        res = 0\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i]==0:\n",
    "                res += customers[i]\n",
    "                customers[i] = 0\n",
    "        res1 = 0\n",
    "        l,r,cur = 0,0,0\n",
    "        while r<len(customers):\n",
    "            cur += customers[r]\n",
    "            if r-l+1>=minutes:\n",
    "                res1 = max(res1,cur)\n",
    "                cur-=customers[l]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return res+res1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        ori = 0\n",
    "        for i in range(len(customers)):\n",
    "            ori+=customers[i]*(1-grumpy[i])\n",
    "            if grumpy[i]==0:\n",
    "                customers[i]=0\n",
    "        new = sum(customers[0:minutes])\n",
    "        ans = new\n",
    "        for i in range(minutes,len(customers)):\n",
    "            new += customers[i]\n",
    "            new -= customers[i-minutes]\n",
    "            ans = max(new,ans)\n",
    "        return ori + ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        orange_sum = 0\n",
    "        for i in range(n):\n",
    "            if grumpy[i] == 0:\n",
    "                orange_sum += customers[i]\n",
    "                customers[i] = 0\n",
    "        \n",
    "        change_sum = sum(customers[:minutes])\n",
    "        tmp = change_sum\n",
    "        right = minutes\n",
    "        while right < n:\n",
    "            tmp += customers[right] - customers[right-minutes]\n",
    "            right += 1\n",
    "            change_sum = max(tmp, change_sum)\n",
    "        return change_sum + orange_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n=len(customers)\n",
    "        cnt=0\n",
    "        for i in range(n):\n",
    "            if i<minutes:\n",
    "                cnt+=customers[i]\n",
    "            else:\n",
    "                cnt+=customers[i]*(1-grumpy[i])\n",
    "        ans=cnt\n",
    "        for i in range(minutes,n):\n",
    "            if grumpy[i]==1:\n",
    "                cnt+=customers[i]\n",
    "            if grumpy[i-minutes]==1:\n",
    "                cnt-=customers[i-minutes]\n",
    "            ans=max(ans,cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        sum_ = 0\n",
    "        for i in range(n):\n",
    "            sum_ += customers[i] * (1 - grumpy[i])\n",
    "        curvalue = 0\n",
    "        for i in range(minutes):\n",
    "            curvalue += customers[i] * grumpy[i]\n",
    "        resvalue = curvalue\n",
    "        for i in range(minutes, n):\n",
    "            curvalue = curvalue + customers[i] * grumpy[i] - customers[i - minutes] * \\\n",
    "            grumpy[i - minutes]\n",
    "            resvalue = max(curvalue, resvalue)\n",
    "        return sum_ + resvalue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(\n",
    "        self, customers: List[int], grumpy: List[int], minutes: int\n",
    "    ) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i] == 0:\n",
    "                res += customers[i]\n",
    "                customers[i] = 0\n",
    "        max_res = 0\n",
    "        for i in range(len(customers)):\n",
    "            if i < minutes:\n",
    "                res += customers[i]\n",
    "                max_res = res\n",
    "            else:\n",
    "                res = res + customers[i] - customers[i - minutes]\n",
    "                max_res = max(max_res, res)\n",
    "        return max_res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i]==0:\n",
    "                res += customers[i]\n",
    "                customers[i] = 0\n",
    "        res1 = 0\n",
    "        cur = 0\n",
    "        l,r = 0,0\n",
    "        while r<len(customers):\n",
    "            cur += customers[r]\n",
    "            if r-l+1>=minutes:\n",
    "                res1 = max(res1,cur)\n",
    "                cur -= customers[l]\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return res + res1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        bumanyi_c = customers\n",
    "        ans = 0\n",
    "\n",
    "        for i,g in enumerate(grumpy):\n",
    "            if g ==0:\n",
    "                ans += customers[i]\n",
    "                bumanyi_c[i] = 0\n",
    "        \n",
    "        bumanyi_num = sum(bumanyi_c[:minutes])\n",
    "\n",
    "        for right,c in enumerate(bumanyi_c[minutes:],minutes):\n",
    "            left = right-minutes\n",
    "            bumanyi_num = max(bumanyi_num,sum(bumanyi_c[left+1:right+1]))\n",
    "\n",
    "\n",
    "        return ans+bumanyi_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        N = len(customers)\n",
    "        sum_ = 0\n",
    "\n",
    "        for i in range(N):\n",
    "            if grumpy[i] == 0:\n",
    "                sum_ += customers[i]\n",
    "                \n",
    "        curValue = 0\n",
    "        \n",
    "        # 先计算起始的 [0, minutes) 区间\n",
    "        for i in range(minutes):\n",
    "            if grumpy[i] == 1:\n",
    "                curValue += customers[i]\n",
    "        \n",
    "        resValue = curValue\n",
    "        # 然后利用滑动窗口，每次向右移动一步\n",
    "        for i in range(minutes, N):\n",
    "            if grumpy[i] == 1:\n",
    "                curValue += customers[i]\n",
    "            if grumpy[i - minutes] == 1:\n",
    "                curValue -= customers[i - minutes]\n",
    "            resValue = max(resValue, curValue)\n",
    "\n",
    "        return sum_ + resValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n=len(customers)\n",
    "        res=0\n",
    "        for i,j in zip(customers,grumpy):\n",
    "            if j==0:\n",
    "                res+=i \n",
    "        for i in range(minutes):\n",
    "            if grumpy[i]==1:\n",
    "                res+=customers[i]\n",
    "        ans=res\n",
    "        for i in range(minutes,n):\n",
    "            if grumpy[i-minutes]==1:\n",
    "                res-=customers[i-minutes]\n",
    "            if grumpy[i]==1:\n",
    "                res+=customers[i]\n",
    "            ans=max(res,ans)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        total = sum(c for c, g in zip(customers, grumpy) if g == 0)\n",
    "        maxIncrease = increase = sum(c * g for c, g in zip(customers[:minutes], grumpy[:minutes]))\n",
    "        for i in range(minutes, n):\n",
    "            increase += customers[i] * grumpy[i] - customers[i - minutes] * grumpy[i - minutes]\n",
    "            maxIncrease = max(maxIncrease, increase)\n",
    "        return total + maxIncrease"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i]==0:\n",
    "                res+=customers[i]\n",
    "                customers[i]=0\n",
    "        l,r,cur,ans=0,0,0,0\n",
    "        while r<len(customers):\n",
    "            cur+=customers[r]\n",
    "            if r-l+1>=minutes:\n",
    "                ans=max(ans,cur)\n",
    "                cur-=customers[l]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return res+ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        original_count = 0\n",
    "        for i in range(n):\n",
    "            if grumpy[i] == 0:\n",
    "                original_count += customers[i]\n",
    "\n",
    "        last_change = 0\n",
    "        for i in range(minutes):\n",
    "            if grumpy[i] == 1:\n",
    "                last_change += customers[i]\n",
    "        best_score = last_change\n",
    "        for i in range(1, n - minutes + 1):\n",
    "            if grumpy[i - 1] == 1:\n",
    "                last_change -= customers[i - 1]\n",
    "            if grumpy[i + minutes - 1] == 1:\n",
    "                last_change += customers[i + minutes - 1]\n",
    "            best_score = max(best_score, last_change)\n",
    "\n",
    "        return best_score + original_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], k: int) -> int:\n",
    "        sums_noangry = 0\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i] == 0:\n",
    "                sums_noangry += customers[i]\n",
    "        # print(sums_noangry)\n",
    "        cur_angry = 0\n",
    "        for i in range(k):\n",
    "            if grumpy[i] == 1:\n",
    "                cur_angry += customers[i]\n",
    "        res_angry = cur_angry\n",
    "\n",
    "        for i in range(k,len(grumpy)):\n",
    "            res_angry = res_angry + customers[i] *grumpy[i] - customers[i-k]*grumpy[i-k]\n",
    "            # if grumpy[i] == 1:\n",
    "            #     res_angry += customers[i] \n",
    "\n",
    "            # if grumpy[i- k] == 1:\n",
    "            #     res_angry -= customers[i-k] \n",
    "            cur_angry = max(res_angry , cur_angry)\n",
    "        return sums_noangry + cur_angry\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n=len(customers)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans+=customers[i]*(1-grumpy[i])\n",
    "        maxx=0\n",
    "        maxx=inc=sum(grumpy[j]*customers[j] for j in range(0,minutes))\n",
    "        for i in range(1,n-minutes+1):\n",
    "            inc+=grumpy[i+minutes-1]*customers[i+minutes-1]-grumpy[i-1]*customers[i-1]\n",
    "            maxx=max(maxx,inc)\n",
    "        return ans+maxx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers, grumpy, X):\n",
    "        \n",
    "        result = buffer = sum([customers[i] for i in range(len(customers)) if grumpy[i] == 0 or i < X])\n",
    "        \n",
    "        for i in range(X, len(customers)):\n",
    "            buffer = buffer + customers[i] * grumpy[i] - customers[i-X]*grumpy[i-X]\n",
    "            result = max(result, buffer)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        start, end = 0, 0\n",
    "        cus = 0\n",
    "        max_num, s = 0, 0\n",
    "        for start in range(len(customers)):\n",
    "            if grumpy[start] == 0:\n",
    "                s += customers[start]\n",
    "            while end < minutes:\n",
    "                if grumpy[end] == 1:\n",
    "                    cus += customers[end]\n",
    "                end += 1\n",
    "            max_num = max(max_num, cus)\n",
    "            if grumpy[start] == 1:\n",
    "                cus -= customers[start]\n",
    "            if end < len(customers) and grumpy[end] == 1:\n",
    "                cus += customers[end]\n",
    "            end += 1\n",
    "        max_num += s\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        base_count = sum(c if not g else 0 for c, g in zip(customers, grumpy))\n",
    "\n",
    "        extra_count = 0\n",
    "        max_extra_count = 0\n",
    "\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i]:\n",
    "                extra_count += customers[i]\n",
    "\n",
    "            if i >= minutes and grumpy[i - minutes]:\n",
    "                extra_count -= customers[i - minutes]\n",
    "            \n",
    "            max_extra_count = max(max_extra_count, extra_count)\n",
    "        \n",
    "        return base_count + max_extra_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        # 1.统计当前满意的人数\n",
    "        n = len(customers)\n",
    "        tot_sum = 0\n",
    "        for i in range(n):\n",
    "            if grumpy[i] == 0:\n",
    "                tot_sum += customers[i]\n",
    "        # 2.最大可增加人数_第一个窗口\n",
    "        max_increase = 0\n",
    "        for i in range(minutes):\n",
    "            max_increase += grumpy[i] * customers[i]\n",
    "        tmp = max_increase\n",
    "        # 2.1其余窗口采用滑出方式\n",
    "        for r in range(minutes, n):\n",
    "            l = r - minutes\n",
    "            tmp += (-grumpy[l] * customers[l] + grumpy[r] * customers[r])\n",
    "            max_increase = max(max_increase, tmp)\n",
    "        return tot_sum + max_increase\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        total_c = 0\n",
    "        for i in range(len(customers)):\n",
    "            if grumpy[i] == 0:\n",
    "                total_c += customers[i]\n",
    "        max_c = total_c\n",
    "        start = 0\n",
    "        for end in range(len(customers)):\n",
    "            if grumpy[end] == 1:\n",
    "                total_c += customers[end]\n",
    "            if end - start + 1 == minutes:\n",
    "                max_c = max(max_c, total_c)\n",
    "                if grumpy[start] == 1:\n",
    "                    total_c -= customers[start]\n",
    "                start += 1\n",
    "        return max_c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        sum_c = 0\n",
    "        for i in range(n):\n",
    "            if grumpy[i] == 0:\n",
    "                sum_c += customers[i]\n",
    "        curValue = 0\n",
    "        # init window\n",
    "        for i in range(minutes):\n",
    "            if grumpy[i] == 1:\n",
    "                curValue += customers[i]\n",
    "        res = curValue\n",
    "        # start\n",
    "        for i in range(minutes, n):\n",
    "            if grumpy[i] == 1:\n",
    "                curValue += customers[i]\n",
    "            # window leaves\n",
    "            if grumpy[i - minutes] == 1:\n",
    "                curValue -= customers[i - minutes]\n",
    "            # max sum\n",
    "            res = max(res, curValue)\n",
    "        return sum_c + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(grumpy)\n",
    "\n",
    "        base_result = sum(customers[i]  for i in range(n) if not grumpy[i])\n",
    "\n",
    "        right = 0\n",
    "        left = 0\n",
    "        \n",
    "\n",
    "        max_result = 0\n",
    "        while left<n:\n",
    "            while (left<n-minutes) and (grumpy[left]==0):\n",
    "                left += 1\n",
    "\n",
    "            if right == 0:\n",
    "                right = left\n",
    "                cur_result = 0\n",
    "\n",
    "            while (right<min(left+minutes, n)):\n",
    "                if grumpy[right]==1:\n",
    "                    cur_result += customers[right]\n",
    "                right += 1\n",
    "\n",
    "            # print(left,right,cur_result)\n",
    "\n",
    "            max_result = max(cur_result, max_result)\n",
    "            cur_result -= customers[left]\n",
    "            left += 1\n",
    "\n",
    "\n",
    "        return max_result+base_result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "\n",
    "        grumpy_customer = [customers[i] if grumpy[i] == 1 else 0 for i in range(len(customers)) ]\n",
    "        # grumpy_customer = [0, 0, 0, 2, 0, 1, 0, 5]\n",
    "\n",
    "        #找滑动窗口里包含grumpy的人数的最大值，即为我们需要使用秘密技巧的时刻\n",
    "        sum_win = sum(grumpy_customer[:minutes])\n",
    "        res = sum_win\n",
    "        temp = minutes-1\n",
    "        for right, x in enumerate(grumpy_customer[minutes:], minutes):\n",
    "            sum_win += x\n",
    "            sum_win-= grumpy_customer[right-minutes]\n",
    "            if sum_win> res:\n",
    "                temp = right\n",
    "                res = sum_win\n",
    "        \n",
    "        left = temp - minutes\n",
    "\n",
    "\n",
    "        for i, x in enumerate(customers):\n",
    "            if (i <left or i > temp) and grumpy[i] == 0:\n",
    "                res += x\n",
    "            elif left<=i<=temp and grumpy[i] == 0:\n",
    "                res += x\n",
    "\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        l, r = 0, 0\n",
    "        happySum = 0\n",
    "        happyInc = 0\n",
    "        maxHappyInc = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            happySum += customers[i] * (1 if grumpy[i]==0 else 0)\n",
    "\n",
    "        while r < n:\n",
    "            happyInc += customers[r] * (1 if grumpy[r] == 1 else 0)\n",
    "            if r - l + 1 >= minutes:\n",
    "                maxHappyInc = max(maxHappyInc, happyInc)\n",
    "                happyInc -= customers[l] * (1 if grumpy[l] == 1 else 0)\n",
    "                l += 1\n",
    "            r += 1\n",
    "\n",
    "        return happySum + maxHappyInc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        l = 0 \n",
    "        n = len(customers)\n",
    "\n",
    "        r = l + minutes-1\n",
    "        tmp = 0\n",
    "        for i in range(r+1):\n",
    "            tmp += customers[i]\n",
    "\n",
    "        for i in range(r+1, n):\n",
    "            if grumpy[i] == 0:\n",
    "                tmp += customers[i]\n",
    "        res = tmp\n",
    "        r += 1\n",
    "        while r < n:\n",
    "            if grumpy[r] == 1:\n",
    "                tmp += customers[r]\n",
    "            l = r - minutes\n",
    "            if grumpy[l] == 1:\n",
    "                tmp -= customers[l]\n",
    "            r += 1\n",
    "            res=max(res, tmp)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        res = 0\n",
    "        cur_res = 0\n",
    "        last_res = 0\n",
    "        for i in range(n):\n",
    "            if grumpy[i] == 0:\n",
    "                res += customers[i]\n",
    "        for i in range(minutes):\n",
    "            cur_res += customers[i] * grumpy[i]\n",
    "        last_res = cur_res\n",
    "        for i in range(minutes, n):\n",
    "            cur_res += customers[i] * grumpy[i]\n",
    "            cur_res -= customers[i - minutes] * grumpy[i - minutes]\n",
    "            last_res = max(last_res, cur_res)\n",
    "        return res + last_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:\n",
    "        N = len(customers)\n",
    "        sum_ = 0\n",
    "        # 所有不生气时间内的顾客总数\n",
    "        for i in range(N):\n",
    "            if grumpy[i] == 0:\n",
    "                sum_ += customers[i]\n",
    "        # 生气的 X 分钟内，会让多少顾客不满意\n",
    "        curValue = 0\n",
    "        # 先计算起始的 [0, X) 区间\n",
    "        for i in range(X):\n",
    "            if grumpy[i] == 1:\n",
    "                curValue += customers[i]\n",
    "        resValue = curValue\n",
    "        # 然后利用滑动窗口，每次向右移动一步\n",
    "        for i in range(X, N):\n",
    "            # 如果新进入窗口的元素是生气的，累加不满意的顾客到滑动窗口中\n",
    "            if grumpy[i] == 1:\n",
    "                curValue += customers[i]\n",
    "            # 如果离开窗口的元素是生气的，则从滑动窗口中减去该不满意的顾客数\n",
    "            if grumpy[i - X] == 1:\n",
    "                curValue -= customers[i - X]\n",
    "            # 求所有窗口内不满意顾客的最大值\n",
    "            resValue = max(resValue, curValue)\n",
    "        # 最终结果是：不生气时的顾客总数 + 窗口X内挽留的因为生气被赶走的顾客数\n",
    "        return sum_ + resValue\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\r\n",
    "        n = len(customers)\r\n",
    "        maxloss = sum(customers[i] for i in range(minutes) if grumpy[i])\r\n",
    "        cur = maxloss\r\n",
    "        j = 0\r\n",
    "        for i in range(1, n - minutes + 1):\r\n",
    "            cur = cur - customers[i - 1] * grumpy[i - 1] \\\r\n",
    "                + customers[i + minutes - 1] * grumpy[i + minutes - 1]\r\n",
    "            if maxloss < cur:\r\n",
    "                maxloss = cur\r\n",
    "                j = i\r\n",
    "        return sum(x for i, x in enumerate(customers) if grumpy[i] == 0 or j <= i < j + minutes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        ans = sum([ customers[i] if g == 0 else 0 for i, g in enumerate(grumpy)])\n",
    "        C = [ c if grumpy[i] == 1 else 0 for i, c in enumerate(customers)  ]\n",
    "        left = 0\n",
    "        right = min(minutes, len(C)) - 1\n",
    "        s = sum(C[left:right + 1])\n",
    "        t = s\n",
    "        while right < len(C) - 1:\n",
    "            right += 1\n",
    "            s = s - C[left] + C[right]\n",
    "            left += 1\n",
    "            t = max(t, s)\n",
    "        return ans + t\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "\n",
    "        grumpy_customer = [customers[i] if grumpy[i] == 1 else 0 for i in range(len(customers)) ]\n",
    "        # grumpy_customer = [0, 0, 0, 2, 0, 1, 0, 5]\n",
    "\n",
    "        #找滑动窗口里包含grumpy的人数的最大值，即为我们需要使用秘密技巧的时刻\n",
    "        sum_win = sum(grumpy_customer[:minutes])\n",
    "        res = sum_win\n",
    "        temp = minutes-1\n",
    "\n",
    "        #找出grumpy_customer里面滑动窗口为3的和的最大值，并记录此刻temp的位置\n",
    "        for right, x in enumerate(grumpy_customer[minutes:], minutes):\n",
    "            sum_win += x\n",
    "            sum_win-= grumpy_customer[right-minutes]\n",
    "            if sum_win> res:\n",
    "                temp = right\n",
    "                res = sum_win\n",
    "        \n",
    "        left = temp - minutes\n",
    "\n",
    "        #遍历customers，将范围不在[left, right]区间，且grumpy[i] == 0 的值加到res 里面，在范围区间的，我们需要+grumpy[i] ==0的值\n",
    "        for i, x in enumerate(customers):\n",
    "            if (i <left or i > temp) and grumpy[i] == 0:\n",
    "                res += x\n",
    "            elif left<=i<=temp and grumpy[i] == 0:\n",
    "                res += x\n",
    "\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\r\n",
    "        n = len(customers)\r\n",
    "        maxloss = sum(customers[i] for i in range(minutes) if grumpy[i])\r\n",
    "        cur = maxloss\r\n",
    "        j = 0\r\n",
    "        for i in range(1, n - minutes + 1):\r\n",
    "            cur = cur - customers[i - 1] * grumpy[i - 1] \\\r\n",
    "                + customers[i + minutes - 1] * grumpy[i + minutes - 1]\r\n",
    "            if maxloss < cur:\r\n",
    "                maxloss = cur\r\n",
    "                j = i\r\n",
    "        return sum(x for i, x in enumerate(customers) if grumpy[i] == 0 or j <= i < j + minutes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        satisfycount =0\n",
    "        pre = [0]\n",
    "        for i in range(len(grumpy)):\n",
    "            if grumpy[i] ==1:\n",
    "                pre.append(pre[-1]+customers[i])\n",
    "            else:\n",
    "                pre.append(pre[-1])\n",
    "                satisfycount+=customers[i]\n",
    "        currentcount = 0\n",
    "        ans = 0\n",
    "        # print(pre)\n",
    "        for i in range(minutes,len(pre)):\n",
    "            currentcount = pre[i]-pre[i-minutes]\n",
    "            if currentcount>ans:\n",
    "                ans = currentcount\n",
    "        # print(satisfycount,ans)\n",
    "        return ans+satisfycount\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        total = sum(c for c, g in zip(customers, grumpy) if g == 0)\n",
    "        maxIncrease = increase = sum(c * g for c, g in zip(customers[:minutes], grumpy[:minutes]))\n",
    "        for i in range(minutes, n):\n",
    "            increase += customers[i] * grumpy[i] - customers[i - minutes] * grumpy[i - minutes]\n",
    "            maxIncrease = max(maxIncrease, increase)\n",
    "        return total + maxIncrease\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        counts = [0 for _ in customers]\n",
    "        pre = [0 for _ in customers]\n",
    "\n",
    "        for i, v in enumerate(customers):\n",
    "            g = grumpy[i]\n",
    "            if g:\n",
    "                counts[i] = 0 \n",
    "                pre[i] = pre[i-1] if i >= 1 else 0\n",
    "            else:\n",
    "                pre[i] += pre[i-1]+v if i >= 1 else v\n",
    "                counts[i] = v\n",
    "\n",
    "        res = 0\n",
    "        l, r = 0, 0\n",
    "        sums = 0\n",
    "        while r < len(grumpy):\n",
    "            sums += customers[r]\n",
    "            if r-l  >= minutes:\n",
    "                sums -= customers[l]\n",
    "                l += 1\n",
    "            left = pre[l-1] if l > 0 else 0\n",
    "            right = pre[-1] - pre[r] if r < len(pre) else 0\n",
    "            res = max(res, sums + left + right)\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "\n",
    "        grumpy_customer = [customers[i] if grumpy[i] == 1 else 0 for i in range(len(customers)) ]\n",
    "        # grumpy_customer = [0, 0, 0, 2, 0, 1, 0, 5]\n",
    "\n",
    "        #找滑动窗口里包含grumpy的人数的最大值，即为我们需要使用秘密技巧的时刻\n",
    "        sum_win = sum(grumpy_customer[:minutes])\n",
    "        res = sum_win\n",
    "        \n",
    "\n",
    "        #找出grumpy_customer里面滑动窗口为3的和的最大值\n",
    "        for right, x in enumerate(grumpy_customer[minutes:], minutes):\n",
    "            sum_win += x\n",
    "            sum_win-= grumpy_customer[right-minutes]\n",
    "            res = max(res, sum_win)\n",
    "        \n",
    "        \n",
    "\n",
    "        #返回总人数-原不满意人数+滑窗里挽回的人数\n",
    "        return sum(customers) - sum(grumpy_customer) + res\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        satis = 0\n",
    "        n = len(customers)\n",
    "        ans = []\n",
    "        if minutes >= n:\n",
    "            return sum(customers)\n",
    "        if 1 not in grumpy:\n",
    "            return sum(customers)\n",
    "        tot = sum([a*(1-b) for a,b in zip(customers,grumpy)])\n",
    "        add = sum(customers[0:minutes]) - sum([a*(1-b) for a,b in zip(customers[0:minutes],grumpy[0:minutes])])\n",
    "        ans = [add]\n",
    "        for i in range(1,n-minutes+1):\n",
    "            add = add-customers[i-1]*grumpy[i-1]+customers[i+minutes-1]*grumpy[i+minutes-1]\n",
    "            ans.append(add)\n",
    "        satis = tot + max(ans)\n",
    "        return satis\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        total = sum(c for c, g in zip(customers, grumpy) if g == 0)\n",
    "        maxIncrease = increase = sum(c * g for c, g in zip(customers[:minutes], grumpy[:minutes]))\n",
    "        for i in range(minutes, n):\n",
    "            increase += customers[i] * grumpy[i] - customers[i - minutes] * grumpy[i - minutes]\n",
    "            maxIncrease = max(maxIncrease, increase)\n",
    "        return total + maxIncrease"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        total_sum, presum = 0, [0]\n",
    "        for i, x in enumerate(customers):\n",
    "            if grumpy[i] == 0:\n",
    "                total_sum += x\n",
    "                presum.append(0 + presum[-1])\n",
    "            else:\n",
    "                presum.append(x + presum[-1])\n",
    "\n",
    "        i, increase_sum = 0, 0\n",
    "        while i+minutes <= len(customers):\n",
    "            increase_sum = max(presum[i+minutes] - presum[i], increase_sum)\n",
    "            i += 1\n",
    "        return total_sum+increase_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        out = 0\n",
    "        missed_idx = []\n",
    "        missed_val = []\n",
    "        for i in range(len(grumpy)):\n",
    "            if grumpy[i] == 1:\n",
    "                missed_idx.append(i)\n",
    "                missed_val.append(customers[i])\n",
    "            else:\n",
    "                missed_val.append(0)\n",
    "                out += customers[i]\n",
    "        incre = 0\n",
    "        for i in missed_idx:\n",
    "            incre = max(incre,sum(missed_val[i:i+minutes]))\n",
    "\n",
    "        return out+incre\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        tsum = 0\n",
    "        for i in range(n):\n",
    "            tsum += (1- grumpy[i]) * customers[i]\n",
    "        print(\"sum: \", tsum)\n",
    "        \n",
    "        value1 = 0\n",
    "        resvalue = 0\n",
    "        for i in range(minutes):\n",
    "            value1 += grumpy[i] * customers[i]\n",
    "        print(\"value1: \",value1)\n",
    "        resvalue = value1\n",
    "        for i in range(minutes, n):\n",
    "            value1 += grumpy[i] * customers[i] - grumpy[i - minutes] * customers[i-minutes]\n",
    "            print(\"value: \",value1)\n",
    "            resvalue = max(resvalue, value1)\n",
    "        return tsum + resvalue\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        # 不满意的总人数\n",
    "        unstatisfy = [c*g for c, g in zip(customers, grumpy)]\n",
    "        # 初始化win_sum\n",
    "        win_sum = sum(unstatisfy[:minutes])\n",
    "        # \n",
    "        ans = win_sum\n",
    "        for right, val in enumerate(unstatisfy[minutes:], minutes):\n",
    "            # a1\n",
    "            win_sum += val\n",
    "            left = right - minutes\n",
    "            # a2\n",
    "            left_num = unstatisfy[left]\n",
    "            win_sum -= left_num\n",
    "            # ans?\n",
    "            ans = max(win_sum, ans)\n",
    "        return sum(customers) - sum(unstatisfy) + ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        l = len(customers)\n",
    "        unsatisfiedCustomers = [0] * l\n",
    "        maxChanged = 0\n",
    "        for i in range(l):\n",
    "            if i == 0:\n",
    "                unsatisfiedCustomers[0] = customers[0] * grumpy[0]\n",
    "            elif i < minutes:\n",
    "                unsatisfiedCustomers[i] = unsatisfiedCustomers[i-1] + customers[i] * grumpy[i]\n",
    "            else: \n",
    "                unsatisfiedCustomers[i] =  unsatisfiedCustomers[i-1] + customers[i] * grumpy[i] - customers[i-minutes] * grumpy[i-minutes]\n",
    "            maxChanged = max(maxChanged, unsatisfiedCustomers[i])\n",
    "        \n",
    "        return sum(customers[i] * (1 - grumpy[i]) for i in range(l)) + maxChanged\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        grumpy_reverse = [1] * n\n",
    "        original_count = 0\n",
    "        for i in range(n):\n",
    "            if grumpy[i] == 1:\n",
    "                grumpy_reverse[i] = 0\n",
    "            else:\n",
    "                original_count += customers[i]\n",
    "\n",
    "        last_change = 0\n",
    "        for i in range(minutes):\n",
    "            if grumpy_reverse[i] == 0:\n",
    "                last_change += customers[i]\n",
    "        best_score = last_change\n",
    "        print(last_change)\n",
    "        for i in range(1, n - minutes + 1):\n",
    "            if grumpy_reverse[i - 1] == 0:\n",
    "                last_change -= customers[i - 1]\n",
    "            if grumpy_reverse[i + minutes - 1] == 0:\n",
    "                last_change += customers[i + minutes - 1]\n",
    "            print(last_change)\n",
    "            best_score = max(best_score, last_change)\n",
    "\n",
    "        print(best_score)\n",
    "        return best_score + original_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "\n",
    "        unsatisfied = [c * g for c, g in zip(customers, grumpy)]\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        window_sum = 0\n",
    "        window_sum = sum(unsatisfied[:minutes])\n",
    "\n",
    "        max_window_sum = window_sum\n",
    "\n",
    "        for right, num in enumerate(unsatisfied[minutes:], minutes):\n",
    "            # A1\n",
    "            window_sum += num\n",
    "\n",
    "            # A2\n",
    "            left = right - minutes\n",
    "            left_sum = unsatisfied[left]\n",
    "            window_sum -= left_sum\n",
    "            \n",
    "            # A3\n",
    "            max_window_sum = max(max_window_sum, window_sum)\n",
    "        \n",
    "        return sum(customers) - sum(unsatisfied) + max_window_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        cur = res = sum(customers[:minutes]) + sum(compress(customers[minutes:], [1 - x for x in grumpy[minutes:]]))\n",
    "        i, j, n = 0, minutes, len(customers)\n",
    "        while j < n:\n",
    "            cur += (customers[j] if grumpy[j] else 0) - (customers[i] if grumpy[i] else 0)\n",
    "            if cur > res:\n",
    "                res = cur\n",
    "            i, j = i + 1, j + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(grumpy)\n",
    "        unhappy = [customers[i]*grumpy[i] for i in range(n)]\n",
    "        happy = sum(customers)-sum(unhappy)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            new_happy = sum(unhappy[i:i+minutes])\n",
    "            ret = max(ret, happy+new_happy)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n = len(customers)\n",
    "        dp = [0] * n\n",
    "        dp[0] = customers[0]\n",
    "        start = 0\n",
    "        pre_sum = [0] * n\n",
    "        pre_sum[0] = customers[0] * (1 if grumpy[0] == 0 else 0)\n",
    "        total_sum = [0] * n\n",
    "        total_sum[0] = customers[0]\n",
    "        for i in range(1, n):\n",
    "            pre_sum[i] = customers[i] * (1 if grumpy[i] == 0 else 0)+ pre_sum[i-1]\n",
    "            total_sum[i] = customers[i] + total_sum[i-1]\n",
    "\n",
    "        for i in range(1, minutes):\n",
    "            dp[i] = dp[i-1] + customers[i]\n",
    "        \n",
    "        for i in range(minutes, n):\n",
    "            prev = dp[i-1] + customers[i] * (1 if grumpy[i] == 0 else 0)\n",
    "            curr = pre_sum[i-minutes] + total_sum[i] - total_sum[i-minutes]\n",
    "            dp[i] = max(prev, curr)\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        # 假设书店老板无法控制不生气，那么不满意的客人数目是恒定的，\n",
    "        # 为sum([customers[i]*grumpy[i] for i in range(n)])，n为书店开张分钟\n",
    "        # 为了使得总的不满意的客人数目尽可能地小，\n",
    "        # 书店老板在连续的minutes分钟中抑制不生气，使得不满意客人数目的减少量要尽可能地大\n",
    "        # 因此把问题转化为了在【长度为minutes的滑动窗口中，使得不满意客人减少量尽可能地大】的滑动窗口问题\n",
    "        \n",
    "        unsatisfied = [c * g for c, g in zip(customers, grumpy)]\n",
    "\n",
    "        win_sum = sum(unsatisfied[:minutes])\n",
    "\n",
    "        max_win_sum = win_sum\n",
    "\n",
    "        for right, num in enumerate(unsatisfied[minutes:], minutes):\n",
    "            win_sum += num\n",
    "\n",
    "            left = right - minutes\n",
    "            win_sum -= unsatisfied[left]\n",
    "\n",
    "            max_win_sum = max(max_win_sum, win_sum)\n",
    "            \n",
    "        return sum(customers) - sum(unsatisfied) + max_win_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        max_cus = 0\n",
    "        n = len(grumpy)\n",
    "        max_anger = 0\n",
    "        anger_cus = []\n",
    "        #不生气\n",
    "        for i in range(n):\n",
    "            anger_cus.append(customers[i]*grumpy[i])\n",
    "            if grumpy[i] == 0:\n",
    "                max_cus += customers[i]\n",
    "        \n",
    "        #计算最大生气区间\n",
    "        for i in range(n-minutes+1):\n",
    "            print(i+minutes)\n",
    "            max_anger = max(max_anger, sum(anger_cus[i:i+minutes]))\n",
    "        return max_cus + max_anger"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        prefix = [0]\n",
    "        for i, j in zip(customers, grumpy):\n",
    "            prefix.append(prefix[-1] + i * (1 - j))\n",
    "        \n",
    "        maxVal = 0\n",
    "        preSum = sum(customers[:minutes-1])\n",
    "        for i in range(minutes-1, len(customers)):\n",
    "            preSum += customers[i]\n",
    "            maxVal = max(maxVal, preSum + prefix[-1] - prefix[i + 1] + prefix[i - minutes + 1])\n",
    "            preSum -= customers[i - minutes + 1]\n",
    "        return maxVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxpool(self, num, pool):\r\n",
    "        temp = sum(pool[:num])\r\n",
    "        ret = temp\r\n",
    "        for i in range(num, len(pool)):\r\n",
    "            temp -= pool[i - num]\r\n",
    "            temp += pool[i]\r\n",
    "            ret = max(ret, temp)\r\n",
    "        return ret\r\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\r\n",
    "        full_nums = sum(customers)\r\n",
    "        if minutes >= len(customers):\r\n",
    "            return full_nums\r\n",
    "        func = lambda x: x[0] * x[1]\r\n",
    "        pool = list(map(func, zip(customers, grumpy)))\r\n",
    "        ret = full_nums - sum(pool) + self.maxpool(minutes, pool)\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        n=len(customers)\n",
    "\n",
    "        unsatisfied=[0 for _ in range(n)]\n",
    "        customers_1=0\n",
    "        for i in range(n):\n",
    "            if not grumpy[i]:\n",
    "                customers_1+=customers[i]\n",
    "            else:\n",
    "                unsatisfied[i]=customers[i]\n",
    "\n",
    "        pref=[0]\n",
    "        for num in unsatisfied:\n",
    "            pref.append(pref[-1]+num)\n",
    "        customers_2=0\n",
    "        for i in range(minutes,n+1):\n",
    "            customers_2=max(pref[i]-pref[i-minutes],customers_2)\n",
    "        return customers_1+customers_2\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        res = 0\n",
    "        n = len(customers)\n",
    "        summ = 0\n",
    "        if n <= minutes :\n",
    "            return sum(customers)\n",
    "        t = [0]*n\n",
    "        s = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            t[i] = customers[i]*grumpy[i]\n",
    "            s[i+1] = s[i] + t[i]\n",
    "        for i in range(n + 1 - minutes):\n",
    "            res = max(res , s[i+minutes]-s[i])\n",
    "        return sum(customers) - s[-1] + res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        grumpy1 = [abs(grumpy[i] - 1) for i in range(len(grumpy))]\n",
    "        temp = [customers[i] * grumpy1[i] for i in range(len(customers))]\n",
    "        ans = sum(temp)\n",
    "        res = sum([customers[i] * grumpy[i] for i in range(minutes)])\n",
    "        res_list = [res]\n",
    "        for i in range(minutes, len(customers)):\n",
    "            if grumpy[i] == 1:\n",
    "                res += customers[i]\n",
    "            if grumpy[i - minutes] == 1:\n",
    "                res -= customers[i - minutes]\n",
    "            res_list.append(res)\n",
    "        return ans + max(res_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        length = len(grumpy)\n",
    "        a = [0]*length\n",
    "        for i in range(length):\n",
    "            a[i] = customers[i] * grumpy[i]\n",
    "        max_sum = 0\n",
    "        max_i = 0 \n",
    "        pre = [0]*(length+1)\n",
    "        for i in range(length):\n",
    "            pre[i+1] = pre[i]+ a[i]\n",
    "        max_pre = 0\n",
    "        max_pre_i = 0\n",
    "        for i in range(minutes, length+1):\n",
    "            if pre[i] - pre[i - minutes] > max_pre:\n",
    "                max_pre = pre[i] - pre[i - minutes]\n",
    "                max_pre_i = i\n",
    "        # print(max_pre_i)\n",
    "        # print(a)\n",
    "        # print(pre)\n",
    "        max_pre_i = max_pre_i-minutes\n",
    "        right = min(max_pre_i + minutes, length)\n",
    "        for i in range(max_pre_i, right):\n",
    "            a[i] = 0\n",
    "        sum2 = 0\n",
    "        for i in range(length):\n",
    "            sum2 += customers[i] - a[i]\n",
    "        return sum2\n",
    "\n",
    "# class Solution:\n",
    "#     def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "#         length = len(grumpy)\n",
    "#         a = [0]*length\n",
    "#         for i in range(length):\n",
    "#             a[i] = customers[i] * grumpy[i]\n",
    "#         max_sum = 0\n",
    "#         max_i = 0 \n",
    "#         for i in range(length):\n",
    "#             sum = 0\n",
    "#             for j in range(minutes):\n",
    "#                 if i+j<length:\n",
    "#                     sum += a[i+j]\n",
    "#             if sum > max_sum:\n",
    "#                 max_sum = max(max_sum, sum)\n",
    "#                 max_i = i\n",
    "#         print(max_i)\n",
    "#         right = min(max_i+minutes, length)\n",
    "#         for i in range(max_i, right):\n",
    "#             a[i] = 0\n",
    "#         sum2 = 0\n",
    "#         for i in range(length):\n",
    "#             sum2 += customers[i] - a[i]\n",
    "#         return sum2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:\n",
    "        \n",
    "        # 使用堆栈存储老板生气时的顾客人数\n",
    "        s = []\n",
    "        res = 0\n",
    "        for i in range(len(grumpy)):\n",
    "            if grumpy[i] == 0:\n",
    "                res += customers[i]\n",
    "            else:\n",
    "                s.append((i,customers[i]))\n",
    "\n",
    "        if len(s) == 0:\n",
    "            return res\n",
    "        # 在老板生气的时间序列中进行滑动窗口，判断在何时抑制生气\n",
    "        res1 = 0\n",
    "        l, r = 0, 0\n",
    "        temp = s[r][1]\n",
    "        l_pre = 0\n",
    "        for l in range(len(s)):\n",
    "            temp -= s[l_pre][1]\n",
    "            while r<len(s) and s[r][0]-s[l][0]+1<=minutes:\n",
    "                temp += s[r][1]\n",
    "                r += 1\n",
    "            res1 = max(res1, temp)\n",
    "            l_pre = l\n",
    "        return res+ res1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
